/* ver: 0.1, date 2-1-2008 by Jeroen S & W
 *  setted up a basic buildalgorithm with all the public methods that were required by the interface
 *  added an encapsulated class that has the location: it is a coordinate pair.
 *  
 *  ver: 0.2, date 2-1-2008 by Jeroen S
 *  Resolved a few warnings
 *  
 *  ver: 0.3, date 2-1-2008 by Jeroen S
 *  Resolved issues with operators that caused issues with 
 *  non-square mazes
 * 
 *  ver: 0.4, date 3-1-2008 by Jeroen S
 *  Made selecting a partner more random (no more clockwise
 *  moving through the directions)
 *  
 *  ver:0.5 , date 4-1-2008 by Jeroen W
 *  isolated coordinatepair in other class
 */

package mazeAssignment;

import java.util.LinkedList;
import java.util.ArrayList;
import java.util.ListIterator;

public class BookBuild implements Build{

	private Maze mazeGrid;
	private ArrayList<LinkedList<CoordinatePair>> gridLocator;
	
	//this is the initialisation
	public void initialise(Maze maze) {
		mazeGrid= maze;
		gridLocator = new ArrayList<LinkedList<CoordinatePair>>();
		int x= mazeGrid.getSizeX();
		int y= mazeGrid.getSizeY();
		
		//set the coordinatepairs for the positions.
		for(int i=0; i<(x*y); i++)
		{ 
			CoordinatePair p = new CoordinatePair(i/y, i%y);
			LinkedList<CoordinatePair> list = new LinkedList<CoordinatePair>();
			list.add(p);
			gridLocator.add(list);
			mazeGrid.getElement(i/y, i%y).setBuildLocation(i);
		}
		
		//sets start and end 
		MazeElement start = mazeGrid.getElement(0, 0);
		//start.setNorth(false);
		//start.setWest(false);
		start.setSolveState(MazeElement.SOLVE_START);
		MazeElement end = mazeGrid.getElement(x-1, y-1);
		//end.setSouth(false);
		//end.setEast(false);
		end.setSolveState(MazeElement.SOLVE_END);
	}
	
	//returns maze structure (optional)
	public Maze getMaze()
	{
		return mazeGrid;
	}


	//returns if it is done (the arraylist should have one element when that is the case:))
	public boolean isDone() {
		return (gridLocator.size() <2);
	}

	//this advances the build one step
	public boolean tick() {
		
		//test if it is done, or it will loop forever (if it is done and we try to tick)
		if(isDone())
		{
			return false;
		}
		
		boolean tickIsDone = false;
		
		//the tick is based on trial and error, we should repeat this until the tick was succesful
		while (!tickIsDone)
		{
			//pick up a random element out of the maze and call it your location
			int i= (int)(Math.random()*gridLocator.size());
			int j= (int)(Math.random()*gridLocator.get(i).size());
			CoordinatePair firstPair= (CoordinatePair)gridLocator.get(i).get(j);
			int ourLocation = mazeGrid.getElement(firstPair.x, firstPair.y).getBuildLocation();
			
			//prepare other variables for the search of the partner (start somewhere randomly
			boolean foundPartner= false;
			boolean doneNorth = false;
			boolean doneEast = false;
			boolean doneSouth = false;
			boolean doneWest = false;
			int partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
			int numpartners = 0;
			int newLocation= -1;
			
			//search for a location that is aside the ourlocation, but that has not been added to the group
			//(list) where "ourlocation" belongs to. if all 4 walls have been searched for and none prevail,
			//then it is time to try to find another one.
			//there are tests for (in order:) out of bounds, same group)
			while (!foundPartner && numpartners < 4)
			{
				
				switch (partner)
				{
				//0 = north
				case 0: 
					doneNorth = true;
					if(firstPair.y==0)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(ourLocation	!= mazeGrid.getElement(firstPair.x, firstPair.y-1).getBuildLocation())
					{
						foundPartner = true;
						mazeGrid.getElement(firstPair.x, firstPair.y-1).setSouth(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setNorth(false);
						newLocation = mazeGrid.getElement(firstPair.x, firstPair.y-1).getBuildLocation();
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//1= east
				case 1:	
					doneEast = true;
					if(firstPair.x==mazeGrid.getSizeX()-1)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(ourLocation	!= mazeGrid.getElement(firstPair.x+1, firstPair.y).getBuildLocation())
					{
						foundPartner = true;
						mazeGrid.getElement(firstPair.x+1, firstPair.y).setWest(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setEast(false);
						newLocation = mazeGrid.getElement(firstPair.x+1, firstPair.y).getBuildLocation();
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//2= south
				case 2:	
					doneSouth = true;
					if(firstPair.y==mazeGrid.getSizeY()-1)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if (ourLocation	!= mazeGrid.getElement(firstPair.x, firstPair.y+1).getBuildLocation())
					{
						mazeGrid.getElement(firstPair.x, firstPair.y+1).setNorth(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setSouth(false);
						newLocation = mazeGrid.getElement(firstPair.x, firstPair.y+1).getBuildLocation();
						foundPartner = true;
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//3= west
				case 3:	
					doneWest = true;
					if(firstPair.x==0)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(ourLocation	!= mazeGrid.getElement(firstPair.x-1, firstPair.y).getBuildLocation())
					{
						foundPartner = true;
						mazeGrid.getElement(firstPair.x-1, firstPair.y).setEast(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setWest(false);
						newLocation = mazeGrid.getElement(firstPair.x-1, firstPair.y).getBuildLocation();
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				case -1:
					numpartners = 4;
					break;
				}
				
			}
			//if all walls have been searched, then it is time for a new element to checkup!
			if(numpartners > 3)
			{
				continue;
			}
			
			//there is a location (ourlocation) and another location that has to be added.
			//by adding the location, we should add the complete list to it!
			
			//search for the list that has the newlocation in it;
			for (int k=0; k<gridLocator.size(); k++)
			{
				CoordinatePair searchPair= (CoordinatePair)gridLocator.get(k).getFirst();
				if (mazeGrid.getElement(searchPair.x, searchPair.y).getBuildLocation()== newLocation)
				{
					//get an iterator to traverse through the linked list which contains the newlocation;
					 ListIterator<CoordinatePair> itr= gridLocator.get(k).listIterator(0);
					 //iterate through the linkedlist and modify all elements on the mazegrid to have the
					 //same buildlocation as the "ourlocation" has.
					 while (itr.hasNext())
					 {
						 CoordinatePair modifyPair = (CoordinatePair) itr.next();
						 mazeGrid.getElement(modifyPair.x, modifyPair.y).setBuildLocation(ourLocation);						 						 
					 }
					
					//add the list from the newlocation to the list from the ourlocation
					 gridLocator.get(i).addAll(gridLocator.get(k));
					//gridLocator.get(i).add(gridLocator.get(k));
					//remove the newlocationlist from the arraylist.
					gridLocator.remove(k);
				}
			}
			//tick has been succesful, no more trial here.
			tickIsDone=true;
			
		}
		//report tick succesful
		return true;
	}
	
	// Selects a random partner, based on the available choices.
	private int selectPartner(boolean doneNorth, boolean doneEast, boolean doneSouth, boolean doneWest)
	{
		int numchoices = 0;
		
		// No partners left to do?
		if(doneNorth && doneEast && doneSouth && doneWest)
			return -1;
		
		// Add a choice for each still unchecked partner.
		if(!doneNorth)
			numchoices++;
		if(!doneEast)
			numchoices++;
		if(!doneSouth)
			numchoices++;
		if(!doneWest)
			numchoices++;
		
		// Choose
		int choice = (int) (Math.random() * numchoices);
		
		// If a partner is available, it was added to the choices
		if(!doneNorth)
		{
			// This is our choice
			if(choice == 0)
				return 0;
			// Prepare for the next
			else
				choice--;
		}
		if(!doneEast)
		{
			if(choice == 0)
				return 1;
			else
				choice--;
		}
		if(!doneSouth)
		{
			if(choice == 0)
				return 2;
			else
				choice--;
		}
		if(!doneWest)
		{
			if(choice == 0)
				return 3;
			else
				choice--;
		}
		/*!NOTREACHED*/
		return -1;
	}
	
	// this is an encapsulated class which contains the x and y positions
	
}
